﻿// 368. 质数 Prime Number（挑战程序设计竞赛）.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


using namespace std;


/*
https://www.papamelon.com/problem/368

给定一个整数n，统计有多少个质数小于等于n，输出质数的个数。

输入
多组测试数据，以 EOF 结束
每组测试占据一行，一个整数
n(1≤n≤999,999)
输出
每组测试数据占据一行，表示质数的个数
提示
一个测试用例最多可能有
1000 个不同的n
测试数据已加强，一些在 Aizu 能通过的代码在这里会 TLE
样例 1
输入
10
3
11
输出
4
2
5
*/

const int N = 1000010;
int primes[N], cnt;
bool st[N];

void get_primes(int n) {
	for (int i = 2; i <= n; i++) {
		if (!st[i]) 
			primes[cnt++] = i;
		for (int j = 0; primes[j] <= n / i; j++) {
			st[primes[j] * i] = true;
			if (i % primes[j] == 0) break;
		}
	}
}


int main()
{
	get_primes(N-1);
	int n;
	while (cin >> n) {
		int l = 0; int r = cnt-1;
		while (l < r) {
			int mid = l + r >> 1;
			if (primes[mid] >= n) r = mid;
			else l = mid + 1;
		}
		if (primes[l] == n)l++;
		cout << l << endl;
	}

}

 